perm filename NSF.F[DOC,TOB]1 blob
sn#027768 filedate 1973-03-01 generic text, type T, neo UTF8
Proposal to
THE NATIONAL SCIENCE FOUNDATION
for
ADVANCED AUTOMATION DEVELOPMENT
by
THE STANFORD ARTIFICIAL INTELLIGENCE LABORATORY
Jerome Feldman, Associate Professor of Computer Science
Associate Director, Artificial Intelligence Laboratory
Principal Investigator
Thomas Binford, Research Associate in Computer Science
Associate Investigator
Richard Paul, Research Associate in Computer Science
Associate Investigator
February 1973
Computer Science Department
School of Humanities and Sciences
STANFORD UNIVERSITY
Stanford, California
ABSTRACT
The Stanford Artificial Intelligence Laboratory proposes to undertake
a program in advanced automation over a period of one year at a cost
of $143,391. This proposal is to continue and extend programs
sponsored under ARPA Contract SD-183.
This proposal is for initial study and preliminary research on a
three year "proof of concept" project in computer controlled
automatic assembly. The outline of the project has been worked out
with industrial and governmental advice, but more analysis as well as
more research is needed.
The project includes a pilot assembly station carrying out practical
assembly tasks, a hardware-software system ready for production, and
fundamental work on the underlying problems of vision, manipulation
and problem-solving. We believe the laboratory is uniquely qualified
to carry out this program which will be an important contribution to
increasing industrial productivity.
Our basic approach involves a general purpose system integrating
sensors and manipulators controlled by sophisticated programs in a
digital computer. We have worked with such systems since 1965 and
have developed many of the basic ideas required in general purpose
assembly devices. The main thrust of this proposal is to establish
the practicality of our methods and carry their development to a
point from which industry can take over.
The research program is divided into four main sections: Pilot
assembly station, vision development, manipulation development, and
systems support. Each section contains a brief description of the
laboratory's past work in the area, how it is to be applied, and what
extensions are to be undertaken. Finally, we consider a number of
important issues concerning our relations with industry and with
other reseach and development efforts in advanced automation.
TABLE OF CONTENTS
Part Page
I The Need for Advanced Automation ......................
II Research Plan .........................................
A. The Pilot Assembly Station ....................
B. Research in Vision ............................
C. Manipulator Development .......................
D. Systems Requirements for Advanced Automation ..
III Dissemination of Results and Relation with Industry ...
IV Staff .................................................
V Computing Facilities ..................................
VI Budget ................................................
VII References ............................................
VIII Relevant Laboratory Publications ......................
IX Films .................................................
X Cognizant Personnel ...................................
I. THE NEED FOR ADVANCED AUTOMATION
The contributions that advanced automation can make to enhance
productivity in manufacturing are now widely appreciated. Current
interest in advanced computer-oriented automation stems from two
sources. The first is the decreasing cost of computation combined
with an improved understanding of how to apply computation to various
aspects of manufacturing. The second cause is the realization that
many current manufacturing operations, primarily assembly and
inspection, will require complex automation methods which are now
research techniques. The same considerations apply to the automation
of tasks such as laboratory and medical procedures, but the emphasis
has been (as ours will be) on manufacturing. A recent ARPA-sponsored
study [Anderson 1972] in which we participated suggests the following
major benefits from advanced automation:
improved national productivity
reduced prices
increased product quality and uniformity
customization of products
increased job satisfaction.
We would like to add just one comment. As we have seen with other
technological developments such as numerical-controlled tools, there
will be things made which were previously impractical to make. There
is widespread agreement in the technical, industrial and government
communities on the potential benefits of advanced automation. There
is much less agreement on the level of sophistication needed in
automation hardware and software. While there are large application
areas in which specially constructed machines or simple general
purpose devices will prove optimal, we believe that the most
practical solution for intermediate quantities (500 to 100,000) will
be to develop general purpose assembly and inspection devices
controlled by sophisticated programs in digital computers.
Several studies have indicated some priorities among directions of
automation. The ISI study [Anderson] indicates that less than 20% of
discrete manufacturing is amenable to special purpose automation. A
Chrysler Corporation study indicates that car assembly labor has
first priority in automation; assembly plant direct labor is 40% of
direct corporate labor. It was felt that automation was essential in
the small parts division. The ISI study quotes a figure of 75% as the
fraction of batch produced discrete manufactures. One conclusion is
that "the emphasis in development should be on simple vision devices
and on low-bandwidth tactile and force sensing feedback". That study
indicates that the assembly process typically accounts for 50 percent
of production cost. Although such estimates are crude, the study
indicates a potential savings of $27 billion on manufactures which
total $492 billion.
We assume that present manipulators have a small but stable market,
and that most will have minicomputers soon (Sundstrand does now).
Will the incremental cost of touch, force and visual sensors be
offset by the opening of new capabilities, and will the cost be
offset by reduced cost of system design for machines which allow
loose alignment tolerances? We estimate that touch and force sensing
will add about 5% to the price of current manipulators of the Unimate
class. We estimate that by 1977, the incremental cost of visual
sensors, a laser ranging device such as we use now,and additional
memory requirements, will add about 15%-20% to current manipulator
prices. If labor costs continue to rise, part of the increase will be
offset, but cost comparisons will not change appreciably over that
time scale unless significant new mechanical designs are made. A
conclusion is that sensor-equipped robots will be available at slight
additional cost. We explore the benefits of incremental improvements
to manipulators.
We do not expect mechanical production costs to drop as dramatically
as electronics costs fall with integration. The most promising cost
reduction development would be high-production standard modules such
as robots. As an example, consider the Stanford arm; produced in
unit quantity, parts, manufacturing and assembly costs are
approximately $10K. The arm is much simpler than an automobile; there
is no reason why it should cost more. A smaller, more recent design
sells for $3500 in quantities of two.
A robot with two arms, minicomputer control, force and touch sensors
could be constructed for under $10K in quantities of 1000 now. To
summarize: two arms (new small Scheinman design) $2000 with hand; arm
drivers and arm interface electronics $1000; force and touch $800;
small computer 8k memory $4500; total $8300. Assuming that the
computer price falls to $1200 by 1978, the cost is $5000. Of course,
these are small arms, suited for parts assembly, not automotive body
assembly. The larger arms, assuming slight redesign for cost
consciousness, would cost about $2500 in units of 1000, for a total
system cost (not price) of $12300, falling to $9000 by 1978. This is
the range of price of present transfer machines which have limited
market because they have limited motion, no control, and are thus
locked out of the economy of scale. There is a dynamic which leads to
economy of scale; the greater the versatility, the wider is the
market for applications. This will be true particularly in small
production and job shop operations which have been difficult to
automate. The larger the production, the more versatility for the
same initial cost as special devices. Also, with high volume,
standardization of maintenance, and availability of parts and service
are improved. The quality of the device is also improved.
The economies of scale in production of assembly modules are matched
by economies of intellectual scale in development of design for
automation. The design process is modularized and easily
communicable; there is a common discipline which can be widely
absorbed; developments of many sources can be integrated. Programming
and training done once for one machine can be transferred to all
machines in a plant, and even transferred nationwide. Functional
modularity has been emphasized in our studies. Modularity is clearly
possible and there is a powerful economic incentive to assemble
widely varying systems from one, two, or three arm modules, force and
touch modules, vision and ranging modules, with planning and
monitoring modules. This would also entail software modularity with
computer-aided mechanical design and job specification for robots on
a local or network time-sharing service.
The alternative is special design for each operation. We expect that
at some point, design will be cheaper with standard robot modules
than with special purpose designs, just as it is now more economical
to use mini-computer controllers than special purpose controllers.
Modularity has the potential to reduce design time and improve
predictability of design time and costs, permitting better planning
and response to competition. To some extent, the dehumanized
industrial worker now fills the role of standard module, so that we
do not expect discontinuous change. The continuity with decades of
experience with design for human versatility in assembly can be
relied upon; robots with some versatility, sensing, contingency
actions, and dexterity will provide a transition to newer schemes
which will evolve more slowly. Another advantage of general purpose
techniques is the ease with which the size of the robot can be scaled
up or down. There appears to be no difficulty in making very large or
very small assembly stations which use essentially the same programs.
Versatile assembly devices have an efficiency advantage in medium
scale and job shop production; their utilization efficiency can be
higher because versatility allows a variety of operations to be
scheduled at one station. The availability of computers for
production scheduling will allow the flexibility to be used to
advantage. Robots would also have longer life over which to amortize
costs, since they could function with greatly changed production
operations, and evolve with new hardware and software modules. They
would have higher reliability, since they would have monitoring,
contingency action, and error recovery. They would be self-aligning,
self-calibrating, and self-testing.
With simple devices, inspection and assembly operations must be
broken down into small operations with transfer operations between.
This introduces extra transfer devices with orientation-preserving or
re-orienting steps, and overlapping operations which can be combined
in an advanced device. The extra cost of jigs and fixtures, and of
stopping assembly lines adds to the cost of special purpose
automation. Robots can cut down on real estate, since several
operations can be done at one station.
Because of the adaptibility of work stations, a quicker response to
market and competition is possible. Production runs can be smaller,
with less capital tied up in inventory and unused machines. There
can be better response to the needs of high technology industry which
often requires small quantities. There has been difficulty in
meeting the tight tolerances necessary for operation of
non-intelligent devices. It is hard to estimate the value of systems
which work within current industrial tolerance, rather than requiring
radical improvements in engineering practice, but that continuity
does seem important.
Serious issues arise in the development of robots with simple sensory
systems. Some evaluation issues should be settled by demonstration,
since much sharper analyses can be made this way. We propose to:
demonstrate practical speed and dexterity with two arms and tool
using. Demonstrate the generality of arm control and planning for
various arms and devices. Demonstrate designs which standardize
interface with devices and which lower interface costs. Demonstrate
programming of assembly devices in an interactive APT-like system
(develop the Stanford Assembly Robot Management System, ARMS); show
the commonality of operations aong similar assembly tasks.
There is already a significant degree of industrial involvement in
computer-aided assembly. GM Research Lab has demonstrated a wheel
mounting operation using visual alignment. IBM has a small robot
project. Hitachi has demonstrated a robot with touch and a system
with visual identification of objects on a conveyor belt, with visual
control of manipulation. Can industry be expected to adequately
support this development? Development of primitive robots is an
evolutionary process, not a single product development. Thus it is
not possible to keep secret and maintain an enormous productivity
advantage; the techniques are usable by everyone. The area is too
big; the payoffs are huge and the investment level is large. Also,
traditionally, industry has been dependent on suppliers. But with the
exception of IBM, the suppliers are smaller and less able to risk the
development. Management techniques require inordinate return on
capital. An alternative support could come again from the military.
The ARPA study and the history of numerical controlled machine tools
are natural consequences of the vast military procurement in
technologically advanced products. In the case of N/C, funds could be
diverted from an outmoded technology to development of devices which
were essential to production plans for the future. It is high
technology products which are most competitive internationally in the
civilian economy. The record of government investment in numerical
control, solid state electronics, computers, and electro-optical
devices has been very productive. However, in large scale development
of civilian products and international markets, foreign governments
have taken the lead. The development of general purpose assembly
devices will benefit manufacturers in a broad spectrum of industry,
particularly medium scale manufacturing. It is an appropriate area
for governmental action to help meet a national need.
Given sensor-equipped robots at little extra cost, they will have
visual ability to sense color, strong contrasts in brightness,
recognize known objects from two dimensional outlines (top view of
flat object) or three dimensionally using depth, to a certain extent
they will be able to recognize three dimensional objects using
monocular recognition. They will be able to visually align mating
parts in assembly operations, increase reliability by self-
calibration and flaw and disaster detection, and permit large
tolerances in parts transfer, even permitting parts to be taken from
a bin. Several of these abilities are not yet available in the
laboratory, but with known conditions and objects, and some
engineering (e.g. color coding) are achievable within the time span
of the proposed project.
The major determinant of the economic impact of assembly robots will
be the extent of their capabilities. Assessing and extending these
capabilities is the principle goal of the proposed project.
II. RESEARCH PLAN
A. THE PILOT ASSEMBLY STATION
The basic goal of the proposed project is to implement a general
purpose assembly station and to prove its applicability to real
problems. The project will be considered a success if one or more
enterprises chooses to manufacture and market the general purpose
station. There are a number of hardware and software problems to be
solved in meeting our goal.
In one configuration, the assembly station is assumed to be connected
to a large time-shared computer facility. Not only does this appear
to be a good design for our problem, but it is also necessary for an
integrated programmed automation facility. The only emphasized
statement in the ARPA study report [Anderson 1972] is: "The maximum
impact of computers in manufacturing will come from complete,
real-time computer cognizance and control of all processes and
resources, allowing the precise scheduling and allocation of these
resources."
Each assembly station will consist of a small digital computer, one
or more manipulators and cameras. Manipulators and cameras will be
combined as modules in systems to suit a given task, and will be
digitally controlled by the station computer. The station computer
may be connected to a central computer or may stand alone. The latter
configuration is less efficient in the long run, but allows for
incremental automation.
The program in the station computer will be flexible as to the number
and position of manipulators and cameras. It will control input from
the cameras, provide for some pre-processing of the picture and the
application of simple tests to the visual data. In the case of
manipulators it will provide for simultaneous servo control. It will
also process other inputs, such as from touch sensors on the
manipulators, from photocell interrupt devices, limit switches, etc.
Both analog and binary outputs will be available for the control of
other devices.
Each station computer will have access to a task program specifying
the actions and tests it should perform to carry out its task. This
task program will be compiled by the central computer. Compilation
will consist of the analysis of predicted scenes in order to specify
simple tests that the station computer can carry out, the calculation
of collision free trajectories for the manipulators, the sequence of
operations and simple contingency plans. etc. We are planning for
tasks whose normal execution does not require detailed scene
analysis. If scene analysis becomes necessary (e.g. a dropped part)
we envision the station sending an image to the central computer for
processing.
The central computer will perform overall control of the individual
assembly stations and the relative rates of production. If at any
station a planned test fails, for which a contingency plan does not
exist, or any unexpected sensor signals are received, the central
computer will also be interrupted and appropriate actions taken. If
the assembly station is not connected to a central computer, these
operations will require human intervention.
Most of the hardware required for the assembly station has been
developed for the laboratory. Manipulators and cameras will be
discussed in detail below. The major additional problem is to refine
the existing designs to meet the demands of an industrial
environment.
We are now acquiring small computer such as the PDP-11 and will
interface the existing arms to it together with one or more cameras.
A software package for the small computer will then be developed in
order to control the manipulators, read the TV cameras and to perform
low level visual analysis. Programs to plan tasks, calibrate the
system and to perform higher level visual analysis, error recovery
and strategy planning will be written in a high level language for
the time-sharing processor.
The most difficult part of the assembly station, and the heart of the
project is a demonstration of the feasibility of the station. We plan
to do this by developing programs which actually assemble and inspect
a variety of fairly complex manufactured items.
A typical example is our current effort, assembly of an automobile
water pump. The major parts are to be located, the screws are
supplied by a feeder, as is standard. Locating the body and cover of
the pump require a gross localization, then a fine localization of
screw holes. Touch provides a final accuracy and independent
coordination of the hand. The placing of alignment pins within screw
holes could be monitored visually; although in this case,the previous
actions provide adequate accuracy. Placing of the cover over
alignment pins can be carried out without vision. Improved force
sensing now under development will be useful for that operation.
As we move to more difficult tasks, the sophistication required goes
up quite rapidly. The current manipulation routines seem to be
expandable to cover anticipated problems, especially since we intend
to employ special purpose manipulators (tools) for some tasks. The
main part of our effort will be vision for assembly; an assembly task
will be performed using vision, touch, and two hands. The vision
effort will be integrated with other abilities, and while no great
generality will be stressed, new modules will be incorporated into
the system, and a set of techniques will evolve. These will depend
heavily on techniques similar to those of our recent studies in
visual feedback and hand/eye coordination [Gill 1972]. The internal
model of the world will be used to predict visual appearance of
selected areas of the scene, and a set of verification procedures
will confirm or contradict the predictions. Many of the operations
will be connected with supplying feedback to manipulation, for
alignment and insertion. These visual procedures will have models for
the parts and approximate locations.
This and other visual tasks connected with assembly will initially be
performed as special case problems. In addition, to make these
techniques available, we will pursue development of strategy
programs. This step is essential if intelligent assembly devices are
to be conveniently programmed for complex tasks. Within the division
of labor between large and small machines, this facility must reside
in the central time-sharing facility which has large memory, file
storage, and problem-solving languages. The system must have a model
of the parts for assembly,and a sequence of instructions for
assembly. It will be necessary to have a representation of shape and
models for usual assembly operations such as insertion and alignment,
and the ability to solve simple problems in connection with these
operations, all this to enable convenient communication with the
user. When these facilities exist, the addition of new features and
operations can be incorporated smoothly, so that users can call on a
growing library of planning modules. The result of a planning effort
is a cycle of machine planning and man-machine interaction which
results in a plan network for the mini computer which controls
individual machines.
B. RESEARCH IN VISION
Research in computer vision has progressed so that the larger part of
our effort is directed toward vision in real scenes. We outline past
research, including work on visual feedback, development of useful
modules, analysis of some outdoor scenes, interpretation of scenes
with curved objects, and a study of sensor systems.
Our past work on visual feedback [Gill 1972] in stacking blocks and
inserting objects in holes is directly relevant to vision for
assembly. The issues involved are: coordinating hand and eye,
utilizing incremental accuracy of vision and manipulation, accurate
prediction to limit search, and limiting accumulation of errors.
Visual guidance in picking up objects and stacking or inserting
objects overcomes errors in the visual and arm coordinate systems,
and errors in correspondence between the two coordinate systems. This
was done under realistic conditions, with the hand still holding the
object and in view; the system predicts the appearance of edges and
corners within a small window around the edges to be aligned, and
uses a corner/edge finder to determine alignment error. The arm makes
accurate incremental error correction. If predictions can be made
accurately, the search window can be small, which increases the speed
of response and decreases possibility of confusion with other areas
of the scene. A major limitation to accuracy of prediction (and to
long-term reliability in the industrial environment) is drift of
calibration. That work incorporates calibration updating by
self-calibration to coordinate hand and eye coordinate systems and
provide for reliability, as well as to limit search by accurately
predicting expected features. Visual feedback with stereo vision is
much more powerful than without; we have demonstrated stereo visual
feedback in a program [Binford unpublished].
We have a set of visual modules to be used in a goal-directed way.
These modules answer questions which arise in practical visual
feedback tasks, and in analysis of outdoor scenes. Are there color
edges in a selected window? Are there edges in brightness? What is
the color of the region in the window? Several preliminary color
region analysis programs have been developed [Binford, unpublished,
Bajcsy 1972]. An edge operator [Hueckel 1969] and a region-based
corner/edge finder [Gill 1972] both operate on small windows of the
scene, as directed by a higher level. An edge verifier is used to
confirm or reject edges predicted from context [Tenenbaum 1970].
Color identification has long been demonstrated. Recently, a program
has been implemented [Thomas unpublished] based on Land's Retinex
model of color constancy in vision, which defines a color triangle
from ordering of brightnesses. The center of the triangle is
designated as white. The program shows a color constancy similar to
humans; table top scenes are assigned colors reasonably well under a
variety of lighting with different spectra: sunlight, flourescent,
and incandescent.
Understanding outdoor scenes is a more complex task than many
industrial visual operations, but it has utility for planetary
exploration; it is also a useful exercise for developing color,
texture, and stereo operations. Bajcsy analyzed outdoor scenes with a
combination of color and texture region analysis [Bajcsy 1972]; depth
cues were taken from the gradient of texture. An attempt was made to
obtain consistent interpretations by making three dimensional
interpretations, and confirming boundaries by independent properties.
Natural objects and natural scenes have been used for our work with
motion parallax [Nevatia in draft] and stereo vision
[Quam,Hannah].These are complementary techniques of depth perception
which are applicable for planetary exploration and industrial tasks.
Motion parallax can be used for planning of navigation and
characterizing large scale terrain features, since it provides large
baselines.
Another aspect of vision with direct application to industrial
enviroments is explored in our work with curved objects. Current
programs use depth information to make useful descriptions of objects
like a doll, a toy horse, a snake, or a glove [Agin]. Programs can
segment these objects into parts like legs, arms or fingers, and link
these parts together to form descriptions of entire objects
[Nevatia]. These operations are precursors to a recognition process.
The work depends on a new representation of shape [Binford 1971] in
terms of volume components and a part/whole segmentation. Primitive
parts are described by an axis which is a space curve, and normal
cross sections along the axis. The representation is based on a
formalism, "generalized translational invariance". There are
significant theoretical reasons why this representation leads to a
natural choice of parts by simple procedures, in distinction to other
suggested representations. We developed a laser ranging device
[Binford 1970,Agin] which was operational two years ago. It is
particularly interesting that the device adds a cost of only about
$400 to the cost of a visual system.
A study of visual and depth ranging sensor has been carried out which
provides a background for choosing sensors and interface, and making
cost estimates [Binford 1972, Earnest 1967]. We have maintained a
calibrated hand and vision system for several years [Sobel 1970], and
have developed self-calibration techniques with one and two eyes
[Yakimovsky unpublished, Hannah 1972, Gill 1972].
A system for understanding scenes of blocks from single views has
been implemented [Falk 1970]; it segments objects, matches against
internal models, predicts appearance from its assumptions, and
searches for verification and contradiction based on the predicted
image. Support and spatial relations are also obtained. There has
been past work on programs to obtain line drawings as input to
recognition systems. An earlier system was based on limited context
of expecting continuation of edges at vertices and predicting missing
edges in certain expected configurations [Grape 1970]. A more recent
approach has been to use models within the process of generating line
drawings, so that the most efficient next guess can be made and
context used intrinsically in the formation of line drawings.
VISION FOR ASSEMBLY
This is a key part of the proposed project. We propose to evaluate
and implement visual facilities required by a robot with simple
vision, in conjunction with force and touch. These facilities must be
modularized by working out several examples, and made fast enough and
small enough to be practical for a minicomputer-based robot. We have
considerable experience with such standardization, and with visual
feedback techniques in the domain of blocks. We are now at work on
extending visual feedback techniques to typical assembly tasks. We
are also evaluating methods of automating visual feedback. We have
well-developed systems for modeling objects from the console and to
predict their appearance using techniques from computer graphics
[Baumgart 1972a,b]. We can predict curved edges from our models. We
will use simple region analysis programs and edge operators to locate
curved edges predicted within a small window. Automated visual
feedback would combine with evolving strategy programs in an
interactive system, Assembly Robot Management System, ARMS. We will
maintain a calibrated system and improve calibration updating so that
reliability is maintained at a high level.
We have developed a special case program for locating the pump body
in the pump assembly and moving it to the standard location. We are
at work on several other such tasks involved in the pump assembly
which contain components of general utility for visual feedback.
These tasks are typical of the simple visual operations which we will
implement or adapt.
VISION RESEARCH
While continuing research activities are not to be supported by the
proposed project, in all likelihood, the research will suggest useful
programs for the assembly system, particularly work in recognition of
complex objects using depth data. The computer now has symbolic
internal models of objects. We are now in a position to recognize
objects such as a glove, a hammer, etc. We will immediately deal
with matching descriptions for recognition. The important extensions
we wish to deal with are occlusion and access to a large visual
memory. These will involve matching of partial descriptions and
encoding of partial descriptions as indices to a small class of
similar shapes, which can then be compared in more detail. We are
working toward making the hardware stable enough that it can maintain
calibration, and software streamlined so that the depth measurement
system can be integrated with other hand/eye facilities. We intend
to apply large parts of our programs for description and recognition
of curved objects using only monocular intensity information. This is
a much harder problem, but within our representation, shares much of
the same code, and relies on the same conceptual basis of local
three-dimensional models.
There is a growing effort on navigation of vehicles in outdoor
scenes. While this is not directly relevant to the industrial
environment, it does reflect the growing involvement in complex
visual tasks, and will lead to further development of an integrated
visual system. One approach which has already given initial results
[Yakimovsky] is to combine region growing with interpretation using a
world model. Thus, regions are combined not simply on the basis of
uniformity but because combining them improves the interpretation. At
the same time, we will be combining more facilities into these visual
systems, and more usable knowledge in the world model.
C. MANIPULATOR DEVELOPMENT
Manipulator research began at Stanford Artificial Intelligence
Laboratory in 1965 with the acquisition and programming of a
prototype Rancho Orthotic Arm. A later version of this arm was used
in vision directed block stacking programs.
Our present arm, the result of a continuing design project, replaced
the Rancho Arm in 1970. This arm like its predecessor was controlled
by a digital servo program running under the time sharing computer.
The new arm was used in the "Instant Insanity" demonstration in 1971.
A second arm of the same type, with only minor modifications, is
currently being interfaced to the computer. Both arms will share a
common work space and will be able to be used individually, or
together for two handed tasks.
Each joint of the arm is calibrated in terms of torque versus drive
level and it is possible to predict the joint drive levels to produce
a given force at the hand. Further, for the hand to exhibit degrees
of freedom of motion, various joints are selected to be "free", that
is to have no position feedback applied to them. By exerting a force
at the hand and providing that certain degrees of freedom exist it is
possible to perform a much wider class of tasks than simple
positional control, for instance screwing in screws, mating parts,
inserting tools and turning cranks.
Touch sensors on the fingers allow the hand to sense objects without
disturbing them. When activated the arm will stop when any of the
sensors touch. Branching arm instructions can test the state of the
sensors and modify the execution of an arm program. When screwing a
nut onto a bolt, for instance, the hand is first centered over the
bolt by touching it.
Control of the arms is by a series of high level instructions; these
instructions may be executed directly, or may be assembled together
into an arm program. Arm programs may then be executed, as desired,
by the control program. The control instructions may be accessed
directly by other programs, using the message procedure mechanism, or
in the form of symbolic source file.
Positional accuracy at the hand is typically 0.1 inches with
repeatability of 0.02 inches. Force control at the hand is within 10
ounces. The data rate to run the arm from an assembled arm program is
of the order of 100 bits/second.
Manipulator research moves ahead simultaneously on three fronts:
control, primitives and devices. Tasks are translated into an
existing hand language and where the task cannot be accomplished in
terms of existing primitives, new primitives are formulated in a
consistent manner. When a new primative is formulated, real time
routines are developed to perform the action. This also leads, in
many cases, to the development of new hardware. Also as new
developments occur in hardware design, existing real time routines
are either re-written or modified.
Research is now concentrating on the following areas:
Strain gauge instrumentation of the wrist, in order to allow for more
sensitive interaction of the hand with a task. High resolution,
high sensitivity touch sensors, to increase tactile recognition and
control abilities. These developments will lead in turn to new
control concepts.
Development of tools for the hand. These tools can be instrumented
such that the computer can feel and or see at the end of the tool.
This should be a very important area of research as it goes beyond
present human capabilities.
Two handed arm control, the planning and execution of tasks requiring
the coordinated motion of both arms. This will require an extension
of the existing servo program and the analysis of synchronization
problems. The development of collision avoiders, so that arms will
not collide with other objects and with each other.
Modification of the existing arm design to provide for better
incremental motions, more degrees of freedom and a more rugged design
suitable for industrial use. Development of arm and eye computer
interfaces. These contain synchronized analog/digital converters
for input and current controlled drivers for output.
The development of new hands is expected as more complex tasks are
attempted. At present, with only one hand, we have been performing
the positioning type of hand actions. When the second arm is
operational we will be able to perform holding and pulling actions as
well.
D. SYSTEM REQUIREMENTS FOR ADVANCED AUTOMATION
A key element in the development of any large programming effort is
the software support. There has been continual effort along these
lines at the Stanford Artificial Intelligence Laboratory and many
useful ideas have been developed. We propose to extend the research
along two separate lines: support for research and system software
for operating automated systems. We will briefly describe our past
efforts in this area and what we propose to undertake.
The Stanford Artificial Intelligence Laboratory has pioneered in
several areas of system programming, including timesharing sys36700
interactive graphics, and programming languages.
A great deal of additional effort has gone into direct support of
hand-eye research. Very early, we established a set of standard
formats and library routines [Pingle 72a]. A programming language,
SAIL[Swinehart], was implemented in 1968. The language incorporates
special features for large real-world-oriented problem solving
systems and is currently in use at a number of Artificial
Intelligence and other laboratories.
As we began to assemble larger and more sophisticated collections of
programs, we felt a need for flexible mechanisms for cooperating
sequential processes. The resulting monitor and language features
[Feldman & Sproull 1971] have worked well for us and have been
influential on other projects. Recently, we have added an
additional set of features to SAIL to facilitate non-deterministic
and event-directed programming[Feldman 1972]. The early reactions
to this work, both within the laboratory and without has been very
encouraging.
We expect relatively little work to be needed on further systems
support for basic research. There will undoubtedly be efforts to
take advantage of new hardware and of new programming ideas that may
develop in the course of this program. Almost all of this work
should be covered by other funding.
The development of software for the assembly station will require
more of our effort. The central-local computer configuration
requires code to be resident in the local computer and in the shared
machine. The low level programs in the local machine will not be
modified often, thus we can assume that a compiler resident in the
central machine will suffice. The planning programs and general
vision programs will be resident in the shared system. There are two
possible configurations for the shared computer system: A PDP-10
equivalent machine or a software package in ASA Standard Fortran IV
which will run on any sufficiently large machine. One of the tasks
under this proposal would be to evaluate these two alternatives.
A major share of the programming research effort will be concentrated
on developing a programming system for automated assembly. This will
combine ideas from our past work on languages, representation,
computer graphics and arm control. We view this task as a branch of
the larger effort on automatic programming being undertaken in this
laboratory and elsewhere.
III. UTILIZATION PLAN-DISSEMINATION OF RESULTS AND RELATION WITH
INDUSTRY
There are several other efforts, at varying levels of sophistication,
in the area of computer controlled advanced automation. The Stanford
Artificial Intelligence Laboratory is the oldest and largest of these
and has provided the cutting edge of much of he development. We
intend to continue this role and to lead in the development of a
practical general purpose assembly system and the associated
software.
All of the discoveries made under this grant will, of course, be made
public. We view our role in information transfer in a much broader
way. Having no desire to sell products and services and no clients
with interests to protect, a university laboratory should be
primarily a place for acquiring and spreading knowledge.
The Stanford Artificial Intelligence Laboratory has always considered
information transfer to be one of its primary goals. In addition, to
our published papers and reports, we have made a number of film
reports which have been extensively circulated. There have been
thousands of visitors, ranging from elementary school classes to
major scientific, governmental and industrial missions from many
countries. We have also encouraged extended visits by workers from
other laboratories and from industry. Members of the laboratory staff
have played a major role in the organization of journals, conferences
and seminars in artificial intelligence. Many of our algorithms,
systems, and hardware designs have been adopted by other groups.
The success of the program proposed here depends heavily on
interaction with industry. We will need additional information on
the opportunities for automation and will try to involve manfacturers
in the development of the pilot assembly station. We have good
working relationships with a number of firms and we expect that a
concrete project will help forge the bonds necessary for the transfer
of advanced automation technology from the laboratory.
One promising approach to technology transfer is a staff associates
program. This involves residence of about a year's duration at the
laboratory by industrial scientists. Such a program was used
successfully at the MIT, Electronic's Research Laboratory in the area
of programming systems for numerically controlled tools and design
automation. We have initiated a similar program in the laboratory
(cf Appendix A) and are pursuing additional forms of cooperation.
Appendix A
The Stanford A.I. Lab has been engaged in research on
advanced automation technology. Our work has progressed to the stage
where we are seriously engaged in developing and disseminating
practical applications. To do this effectively, we will need the
help of industrial organizations with computer sophistication and an
understanding of practical problems. One form of cooperation which
we are engaged in is a staff associates program. A staff associate
is a member of another organization in residence at the A.I. Lab. We
have had a number of staff associates over the years, mostly from
foreign countries. The enclosed letter from Japan is typical of the
inquiries we receive. The purpose of the new program is to invite a
few domestic inductrial organizations to submit candidates for the
staff associates positions.
We expect to be able to have three to five staff associates
in the laboratory at a time. The associate would remain for about a
year and would be paid by his sponsoring organization. He would be a
regular member of the laboratory staff, working on automation
problems.
There are, of course, academic programs at Stanford which
could also involve work at the Artificial Intelligence Lab. The
staff associate program differs in that the selection criteria are
different, the timing more flexible, and the expected time devoted to
course work much less. We believe that it is the most effective
mechanism for us to learn from and help industrial practitioners of
computer-aided advanced automation.
Jerome A. Feldman
IV. STAFF
Brief Biographical Sketches
Jerome A. Feldman, Principal Investigator: Early training in physics
and mathematics; Ph.D. in computer science from Carnegie-Mellon,
1964. Two years at M.I.T. Lincoln Laboratory. At Stanford since 1966,
leader of Robotics group since 1968. currently Associate Professor of
Computer Science and Associate Director of the Artificial
Intelligence Lab. Research interests include Robotics, associative
processing, inductive inference, and Translator-writing systems.
Thomas O. Binford, Associate Investigator: Received PhD in physics
from the University of Wisconsin, 1965, working with strange particle
reactions, Regge pole and group theory phenomenology. Fulbright
1965-66 Tata Institute of Fundamental Research, Bombay, India: phase
shift analysis of strange particle systems; theory of unstable
particles. At MIT Artificial Intelligence Project 1967-70, working
on representation of shape, region-based analysis system and other
areas of computer vision, systems programming for LISP. Lecturer in
computer science at Stanford University. Research interests are
computer vision, robotics, representation, and perception.
Richard P. C. Paul, Associate Investigator: Undergraduate work in
Engineering Physics at McGill, Masters in Electrical Engineering and
PhD in Computer Science at Stanford University. From 1963 at the
Stanford Linear Accelerator Center as Electronic Engineer. At the
Stanford A. I. Laboratory since 1966 and responsible for manipulator
systems development since 1968. Research interests include Robotics
and digital servo systems.
John McCarthy: BS in Math., Cal Tech, PhD in Math, Princeton, 1951.
With Minsky, organized and directed the Artificial Intelligence
Project at MIT. Joined Stanford as Professor of Computer Science in
1962. Organized and directs the Stanford Artificial Intelligence
Lab. Research interests include nearly all aspects of artificial
intelligence, timesharing systems, mathematical theory of
computation, and representation theory.
Victor Scheinman: Bachelor's in Electrical Engineering, M.I.T.,
Engineer's in Mechanical Engineering from Stanford, 1969. Employed
as a design engineer at Stanford, M.I.T., and Raychem since 1969.
Responsible for the design and construction of computer controlled
arms, as well as other Robotics equipment such as color-wheels, focus
controls, pan-tilt heads, etc.
Lester Earnest: BS in Electrical Engineering, Cal Tech; MS in
Electrical Engineering, MIT, 1960. Two years at MIT Lincoln
Laboratory. Seven years at Mitre Corporation, ending as Head of
Information Systems Department. At Stanford since 1965 as Executive
Officer and Associate Director of the Artificial Intelligence
Laboratory, Research Computer Scientist, and Lecturer in Computer
Science. Responsible for administration and industrial liason.
Curriculum Vitae
JEROME A. FELDMAN
1972
Biographical Information:
Born: December 5, 1938 in Pittsburgh, Pennsylvania, U.S.A.
Nationality: United States
Marital Status: Married, two children
EDUCATION:
B.A. (Physics, with Distinction) Rochester 1960
M.A. (Mathematics) Pittsburgh 1961
Ph.D. (Mathematics, Computer Science) Carnegie-Mellon 1964
HONORS AND SOCIETIES:
Association for Computing Machinery
American Association for the Advancement of Science
National Lecturer, Association for Computing Machinery 1966
Best Session Award, IEEE, August 1970
Fulbright Lecturer, Hebrew University, Jerusalem 1970-71
PROFESSIONAL EXPERIENCE:
Engineer, Westinghouse Electric Corporation 1960-61
Asst. Research Scientist, Carnegie-Mellon U. 1963-64
Staff Member, MIT Lincoln Laboratory 1964-66
Summer Lecturer, U. Pennsylvania 1966
Summer Lecturer, U. Michigan 1967
Asst. Prof., Computer Science, Stanford U. 1966-69
Assoc. Prof., Computer Science, Stanford U. 1969-Present
Visiting Prof. of Computer Science, Hebrew U. 1970-71
Assoc. Dir., Artificial Intelligence Lab., Stanford U. 1972-Present
EDITORIAL, ORGANIZATIONAL, AND CONSULTATION:
Reviewer for Computing Reviews, Journal and
Communications of the ACM, Information and
Control, IEEE Computer Group, various Conferences
and government agencies.
Consultant for IBM, Systems Development Corp.,
Martin-Marietta Corp., Lockheed Missiles and Space
Corp., General Motors, National Institute of Health
Editorial Board, Fundamental Studies in Computer
Science, North-Holland Publishing Company
Lecturer, ACM Professional Development Seminar in
Time-Sharing, 1967
Organizing Committee, Israel Alta Conference,
Ashkelon, February 1971
NATO Conference on Software, Rome,Italy,1969
ACM Conf. on Very High Level Languages, 1974
PUBLICATIONS
Jerome A. Feldman
"Some Regularity Theorems on Kernel Methods of Summation for
Functions of a Complex Variable," Masters' Thesis, U. of Pittsburgh,
1961.
"A Formal Semantics for Computer Oriented Languages", Ph.D.
Dissertation, May 1964, Carnegie-Mellon University.
"Aspects of Associative Processing", TN-1965-13, Lincoln Laboratory,
Massachusetts Institute of Technology, Lexington, Massachusetts.
"A Formal Semantics for Programming Languages", Proceedings of the
International Federation of Information Processing Societies, May
1965.
"A Formal Semantics for Computer Languages and its Applications in a
Compiler-Compiler", Communications of the Association for Computing
Machinery, Vol. 9, No. 1, January 1966, and reprinted in "COMPUTER
COMPILER TECHNIQUES", Auerbach Publishers, 1971.
"An Associative Processing System for Conventional Digital
Computers", (with P.D. Rovner), TN-1967-19, Lincoln Laboratory, MIT,
Lexington, Mass.
"The Compiler-Compiler in a Time-Sharing Environment", (with J.
Curry), Summer Lectures on Advanced Computer Organization, University
of Michigan, June 1967. Also Bit Dropper, September 1967.
"Translator Writing Systems", (with D. Gries), CS 69, Computer
Science Department, Stanford University, June 1967.
"First Thoughts on Grammatical Inference", A.I. Memo 55, Stanford
University, August 1967.
"Translator Writing Systems", (with D. Gries), Communications of the
Association for Computing Machinery, Vol. 11, No. 3, March 1968, and
reprinted in "Computer Compiler Techniques", Auerbach Publishers,
1971.
"The Leap Language and Data Structure", (with P.D. Rovner), Lincoln
Laboratory Memorandum, January 1968. Also in reduced form in
Proceedings of the International Federation of Information Processing
Societies, August 1968.
"Grammatical Inference and Grammatical Complexity", (with others), CS
125, Stanford University, Computer Science Department, Stanford,
California, May 1969.
"An Algol-based Associative Language", (with P.D. Rovner), A.I. Memo
66, Stanford University, 1968. Also Communications of the ACM, Vol.
12, No. 8 August 1969, pp. 439-449. Reprinted in, INTRODUCTION TO
INFORMATION SCIENCE (T. Saracevic, Ed.) Bowker, 1971.
"The Stanford Hand-Eye Project", (with others), Proc. First
International Congress on Artificial Intelligence, Washington, D.C.,
May 1969.
"The Computer Description of Simply Described Scenes", (with R.P.
Paul and G. Falk), A.I. Memo 101, Stanford University. Also in,
PERTINENT CONCEPTS IN COMPUTER GRAPHICS, (J. Nievergelt and M.
Faiman, Eds.), U.of Illinois Press, 1969.
"Machine Intelligence", Review of Numbers I.III of the Machine
Intelligence Series, Information and Control, 14, 490-492, 1969.
"Towards Automatic Programming", Preprints of the NATO Software
Engineering Conference, Rome, Italy, 1969.
"Getting a Computer to See Simple Scenes", IEEE Student Journal,
September 1970.
"A Survey of Grammatical Inference", (with A. Biermann), Proceedings
of International Congress on Pattern Recogniton, Honolulu, January
1971. also in S. Watanbe (Ed.) FRONTIERS OF PATTERN RECOGNITION,
Academic Press, 1972.
"Hebrew University Production Language", (with S. Tsur and D. Lehman)
Hebrew University, Computer Science Department, February 1971.
"A Way of Looking at Things", Hebrew University, Computer Science
Department, February 1971.
"A Laboratory for Hand-Eye Research", (with others), Proceedings
IFIPS International Conference, Lubljana, Yugoslavia, August 1971.
"System Support for the Stanford Hand-Eye Project", (with R. Sproull)
Proceedings Second International Congress on Artificial Intelligence,
London, September 1971, p. 183-189.
"The Use of Vision and Manipulation to Solve the Instant Insanity
Puzzle", (with others), Proceedings Second International Conference
on Artificial Intelligence, London, September 1971, p. 359-364.
"Some Decidability Results on Grammatical Inference and Complexity",
Information and Control, Vol. 20, No. 3, April 1972, p. 244-262.
"On The Synthesis of Finite-State Machines from Samples of their
Behavior", (with A. Biermann), IEEE Transactions on Computers, June
1972, Vol. C-21, No. 6, p. 592-596.
"Automatic Programming", CS 255, Stanford University, Computer
Science Department, Stanford, California, February 1972.
"Total Complexity and the Inference of Best Programs", (with P.
Shields), CS 253, Stanford University, April 1972. Submitted to
Mathematical Systems Theory.
"Recent Developments in SAIL-An Algol Based Language for Artificial
Intelligence", (with others). CS 308, Stanford University, August 1972.
Proc. Fall Joint Computer Conference,Anaheim, Cal.,1972,p.1193-1202.
"Associative Languages" to appear in The Encyclopedia
of Computer Science and Technology, A. Ralston, Ed.
"A Semantics-Based Decision Theoretic Region Analyzer" (with Y.Yakimovsky)
Submitted to Third IJCAI, February,1973
MAJOR PROGRAMMING SYSTEMS DEVELOPED
TRANSLATOR WRITING SYSTEMS
FSL: Additional reference
Itturriaga, R. et.al., "Techniques and Advantages of Using the
formal compiler writing system FSL to implement a Formula Algol
Compiler", Proc. AFIPS Conference 1966, pp. 241-252.
VITAL: Additional Reference
Mondschein, L.F. "VITAL compiler-compiler System Reference Manual",
TN-1967-12. M.I.T., Lincoln Lab., February 1967.
ASSOCIATIVE LANGUAGE SYSTEMS
LEAP: Additional reference
Rovner, P., "The LEAP Users Manual", Mem. 23L-0009, M.I.T., Lincoln
Lab., December 1968.
Swinehart, D. and R. Sproull, "SAIL Users Manual", Operating Note
57.1; Stanford A.I. Project, April 1970.
COOPERATING SEQUENTIAL PROCESSES
HAND-EYE SYSTEM: Additional reference
Pingle, K., "System Manual for Hand-Eye Hackers", Internal
Memorandum, Stanford A.I. Project, June 1971.
DOCTORAL STUDENTS
NAME DEPT. TITLE/TOPIC FINAL ORAL CURRENTLY
F.J. Hilbing Industrial Strategies for 1968 U.S.A.F.
Engineering Paging a Large Academy
Associative Data Base
J.J. Horning Computer A Study of Grammati- 1969 U. of
Science cal Inference Toronto
L.F. Morris Computer Semantic Models and 1969 Syracuse U.
Science Compiler Correctness
G. Falk Computer Computer Interpreta- 1970 Rutgers U.
Science tion of Imperfect
Line Data as a Three-
Dimensional Scene
I. Sobel Electrical Camera Models and 1970 Haifa
Engineering Machine Perception Technion
J.Tenenbaum Electrical Accommodation in 1970 Stanford
Engineering Computer Vision Research
Institute
J.D.Becker Computer An Information 1970 Bolt,
Science Processing Model of Beranek, &
Intermediate Level Newman
Cognition
R. Paul Computer Studies with a 1972 Stanford U.,
Science Computer Controlled A.I. Lab.
Arm
D.Swinehart Computer A One-Level Language 1972 Stanford U.,
Science System A.I. Lab.
A. Gill Electrical Visual Feedback Con- 1972 Israel
Engineering trol of a Mechanical Defense
Arm Establshmnt.
D. Levine Computer Automated Error 1972 Stanford U.
Science Correction of IMSSS
German Sentences
G. Grape Computer Computer Vision 1973
Science Through Sequential
Abstraction
J. Gips Computer Structure of 1973
Science Pictures Applied to
Art and Vision
S.Ganapathy Computer Analysis of Simple 1973
Science Scenes Using Multiple
Views
J. Low Computer Optimization of 1973
Science Data Structures for
Associations
Y.Yakimovsky Computer Knowledge-based, 1973
Science Decision Theoretic
Region Analysis of
Pictures
UNIVERSITY SERVICE
Freshman Seminar, "The Information Revolution" 1967-68
Faculty Senate 1969-70
Presidents Low-Cost Housing Committee 1968-69
Steering Committee, Junior Faculty Forum 1968-69
SWOPSI Seminar, "Computers and Society" 1969-70
Freshman Adviser 1971-72
Committee on Linguistics 1971-72
Lecturer, NSF Summer Program 1971
Faculty Adviser, Student Chapter,
Association for Computing Machines 1966-68
Lecturer, Campus Alumni Conference - May 1970
Departmental Undergraduate Adviser 1972-73
Name: RICHARD P.C. PAUL
Born: June 16, 1936 in Sydney Australia.
Nationality: United States
Marital Status: Married, two children.
EDUCATION:
B.Eng. (Engineering Physics, with Honour) McGill 1963
M.Sc. (Electrical Engineering) Stanford 1968
Ph.D. (Computer Science) Stanford l972
PROFESSIONAL EXPERIENCE:
Electronic Engineer, Stanford Linear Accelerator Center 1963-67
Computer Systems Engineer, Stanford A.I. Laboratory 1967-68
Research Programmer, Stanford A.I. Laboratory 1969-72
Research Associate, Stanford A.I. Laboratory 1972-present
PUBLICATIONS:
"A Multi-pulse Generator for Testing a Radar Beacon", Canadian
Engineering Journal, 1962.
With G. Falk and J. Feldman, "The Computer Representation of Simply
Described Scenes" Memo AIM-101, Computer Science Dept., Stanford
University, Stanford, California.
With Feldman et al, "The Use of Vision and Manipulation to Solve the
Instant Insanity Puzzle", Proc. Second International Joint Conference
on Artificial Intelligence.
"Trajectory Control of a Computer Arm", Proc. Second International
Joint Conference on Artificial Intelligence, 1971.
"Modelling Trajectory Calculation and Servoing of a Computer
Controlled Arm", PhD. Thesis, Computer Science Dept., Stanford
University.
Name: THOMAS O. BINFORD
Born: April 13,1936, Jefferson Twp, Pennsylvania
Nationality: USA
Marital Status:divorced
EDUCATION:
BS physics Pennsylvania State University 1957
PhD physics University of Wisconsin 1965
CURRENT RESEARCH:
Artificial Intelligence Laboratory, Stanford University
laser depth ranging system
representation of shape
recognition of complex objects
efficient method for proximity in n-dimensions
color region analysis
analysis of texture
sensor study
Artificial Intelligence Laboratory, MIT 1967-1970
Topological region analysis
line finder using sequential decision
software for a visual experimentation
recognition of parallelipipeds from incomplete line drawings
two-dimensional shape recognition
line verification
line prediction
POST-DOCTORAL RESEARCH:
Fulbright grant, Tata Institute of Fundamental Research,Bombay India
partial wave analysis of hyperon production by pions;
Regge-pole analysis of Sigma plus production by pions;
theory of unstable particles and symmetry principles
PhD
Strange particle production by pions near 1 Bev/c.
Two new experimental equalities among cross sections;
test of charge independence in hyperon production;
showed adequacy of Regge-pole theory to explain high-energy cross sections;
PUBLICATIONS:
"Structured Descriptions of Complex Objects",R.K.Nevatia and T.O.Binford
Third Int Conf on AI, February, 1973.
Stanford, Calif, 1973.
"Computer Vision", T.O.Binford and J.M.Tenenbaum, Computer, IEEE,
April 1973.
"Sensor Systems for Manipulation", Conference on Remotely Manned
Systems, JPL, Pasadena, Calif, Sept 1972.
"Visual Perception by Computer", Invited paper at IEEE Systems
Science and Cybernetics, Miami, Dec 1971.
With G. Agin, "Representation and Description of Complex Objects", To
be published.
With Feldman, et al, "The Use of Vision and Manipulation to Solve the
Instant Insanity Puzzle", Proc. Second International Joint Conference
on Artificial Intelligence.
With Tenenbaum, et al, "A laboratory for Hand-Eye Research",
IFIP proceedings, August 1971.
"The Vision Laboratory-Part One", MIT AI memo 203.
"The TOPOLOGIST: A Region-Oriented System", (in draft form)
With A. Herskovits, "On Boundary Detection", MIT AI memo 183.
"Display Functions in LISP", MIT AI memo 182.
With Desai, "High Energy Elastic Scattering at Low Momentum Transfers", Physical
Review 138,B1167.
With others, "Experimental Check of Some SU(6) Cross Section Equalities", Physical
Review Letters 14,715.
With others, "Hyperon Production in Pion Interactions", Physical Review (1968).
"Triangle Inequality in Associated Production", Physical Review
(1968).
+ - o
With Anderson, et al, "CP-Nonconserving Decay K ← π π π ", Physical
1
Review Letters 14,475.
o + - o
With Stern, et al, "Absolute Decay Rate for K → π π π and the
2
2
|DI|=1/2 Rule", Physical Review Letters 12,459.
With Lind, et al, "Experimental Investigation of V-A in Leptonic
Lambda Decay", Phys Rev 135,B1483.
DOCTORAL STUDENTS:
G.J.Agin Description and Representation 1972
of Complex Objects
R.K.Nevatia Recognition of Complex Objects 1973
Ruzena Bajcsy (under Prof J. McCarthy)
Computer Identification of Textured 1972
Visual Scenes
T. Garvey Perceptual Problem Solving 1973
V. COMPUTING FACILITIES
The Laboratory operates a display-oriented timesharing system with
facilities for real-time control of mechanical arms and other special
devices. This system is connected to the ARPA computer network.
Central Processor: Digital Equipment Corporation PDP-10
Real-time Processor: Digital Equipment Corporation PDP-6
Network Processor: BBN IMP (Honeywell DDP-516)
Primary Store: 65K words of 1.7 microsecond DEC Core
65K words of 1 microsecond Ampex Core
131K words of 1.6 microsecond Ampex Core
Swapping Store: Librascope disk (5 million words, 22 million
bits/second transfer rate)
File Store: IBM 3330 disc file, 6 spindles (leased)
Peripherals: 4 DECtape drives, 2 mag tape drives, line printer,
Calcomp plotter, Xerox Graphics Printer
Terminals: 58 TV displays, 6 III displays, 3 IMLAC displays,
1 ARDS display, 15 Teletype terminals
Special Equipment: Audio input and output systems, hand-eye
equipment (2 TV cameras, 3 arms), remote-
controlled cart
Nearly all of this equipment was acquired with support from the
Advanced Research Projects Agency for research in artificial
intelligence.
VI. BUDGET
ADVANCED AUTOMATION DEVELOPMENT
RESEARCH GRANT PROPOSAL BUDGET
ONE YEAR BEGINNING JULY 1, 1973
BUDGET CATEGORY
7/1/73-7/1/74
----------------------------------------------------------------------
A. SALARIES & WAGES:
1. Senior personnel:
a. Principal Investigator
J. Feldman, Associate
Professor, (2 mos. FTE) $ 3,624
b. Faculty Associate
J. McCarthy, Professor ---
2. Other Personnel:
a. Research Computer Scientist:
L. Earnest, (2 mos. FTE) 4,584
b. Research Associates:
T. Binford, (3 mos. FTE) 4,650
L. Paul, (3 mos. FTE) 4,410
c. Non-Fac. Professionals (other):
------, Research Programmer,
(12 mos. FTE) 12,000
V. Scheinman, Design Engineer,
(6 mos. FTE) 8,280
d. Grad Students:
Student Research Assts.:
(2) 1/2 time Acad. Yr.,
(9 mos. FTE) 6,120
(2) 100% Summer Qtr.,
(6 mos. FTE.) 4,500
e. Secretarial-Clerical:
(1) Secretary, (6 mos. FTE) 3,900
f. Technical:
(1) Electronics Tech.,
(12 mos. FTE) 9,600
g. Reserve for Salary Increases
@ 5% per year 3,083
______
TOTAL SALARIES & WAGES $ 64,751
B. FRINGE BENEFITS:
16% 7/1/73 to 8/31/73,
17.3% 9/1/73 to 6/30/74 11,062
_______
Total Salaries, Wages and
Fringe Benefits (A + B) $ 75,813
C. EXPENDABLE SUPPLIES AND EQUIP.:
Office Supplies, Xeroxing,
Postage, Freight, Consulting,
Honorariums 1,800
D. TRAVEL:
1. Domestic
Local 600
Other 3,600
_____
Total Travel 4,200
E. PUBLICATION COSTS: 400
F. OTHER COSTS:
1. Communications (telephones) 1,000
2. Equipment Rental (Disk) 15,000
------
Total Other Costs 16,000
______
G. TOTAL DIRECT COSTS (A through F) $ 98,213
H. INDIRECT COSTS:
1. On Campus 46% of Net Total
Direct Costs (G) 45,178
______
I. TOTAL COSTS (G + H) $143,391
-------
-------
ADVANCED AUTOMATION DEVELOPMENT
RESEARCH GRANT PROPOSAL BUDGET
ONE YEAR BEGINNING JULY 1, 1973
BUDGET CATEGORY
7/1/73-7/1/74
----------------------------------------------------------------------
A. SALARIES & WAGES:
1. Senior personnel:
a. Principal Investigator
J. Feldman, Associate
Professor, (2 mos. FTE) $ 3,624
b. Faculty Associate
J. McCarthy, Professor ---
2. Other Personnel:
a. Research Computer Scientist:
L. Earnest, (2 mos. FTE) 4,584
b. Research Associates:
T. Binford, (3 mos. FTE) 4,650
L. Paul, (3 mos. FTE) 4,410
c. Non-Fac. Professionals (other):
------, Research Programmer,
(12 mos. FTE) 12,000
V. Scheinman, Design Engineer,
(6 mos. FTE) 8,280
d. Grad Students:
Student Research Assts.:
(2) 1/2 time Acad. Yr.,
(9 mos. FTE) 6,120
(2) 100% Summer Qtr.,
(6 mos. FTE.) 4,500
e. Secretarial-Clerical:
(1) Secretary, (6 mos. FTE) 3,900
f. Technical:
(1) Electronics Tech.,
(12 mos. FTE) 9,600
g. Reserve for Salary Increases
@ 5% per year 3,083
______
TOTAL SALARIES & WAGES $ 64,751
B. FRINGE BENEFITS:
16% 7/1/73 to 8/31/73,
17.3% 9/1/73 to 6/30/74 11,062
_______
Total Salaries, Wages and
Fringe Benefits (A + B) $ 75,813
C. EXPENDABLE SUPPLIES AND EQUIP.:
Office Supplies, Xeroxing,
Postage, Freight, Consulting,
Honorariums 1,800
D. TRAVEL:
1. Domestic
Local 600
Other 3,600
_____
Total Travel 4,200
E. PUBLICATION COSTS: 400
F. OTHER COSTS:
1. Communications (telephones) 1,000
2. Equipment Rental (Disk) 15,000
------
Total Other Costs 16,000
______
G. TOTAL DIRECT COSTS (A through F) $ 98,213
H. INDIRECT COSTS:
1. On Campus 46% of Net Total
Direct Costs (G) 45,178
______
I. TOTAL COSTS (G + H) $143,391
-------
-------
VII. REFERENCES
[Alexander] Tom Alexander, "The Hard Road to Soft Automation",
[Anderson 1972] R. Anderson,"Programmable Automation, The Future
of Computers in Manufacturing", Datamation, Dec 1972.
[Agin] G. Agin, "Description and Representation of Curved Objects",
Artificial Intelligence Laboratory, Stanford University, AIM-134,
October 1972.
[Bajcsy 1972] "Computer Identification of Visual Texture"
AIM-180,Artificial Intelligence Laboratory, Stanford University,
October 1972.
[Baumgart 1972a] B. Baumgart, "GEOMED - A Geometric Editor", May 1972.
SAILON-68,Artificial Intelligence Lab, Stanford University,
[Baumgart 1972b] Baumgart, Bruce G., WINGED EDGE POLYHEDRON REPRESENTATION,
AIM 179,Artificial Intelligence Lab, Stanford University,October 1972.
[Binford 1972]"Sensor Systems for Manipulation", Conference on Remotely
Manned Systems, JPL, Pasadena, Calif, Sept 1972.
[Binford 1971] "Visual Perception by Computer", Invited paper IEEE
Systems Science and Cybernetics, Miami, Dec 1971.
[Binford 1970] T.O.Binford, "Ranging by Laser", Internal Report,
Artificial Intelligence Lab, Stanford University, Oct 1970.
Clowes, M.B.[1971] "On Seeing Things" AI Journal.
[Earnest 1967] L.D.Earnest,"Choosing an eye for a Computer";
AI Memo 51, Artificial Intelligence Lab, Stanford University, 1967.
[Falk 1971] G. Falk, "Scene Analysis Based on Imperfect Edge Data", Proc. 2IJCAI,
Brit. Comp. Soc., Sept. 1971.
[Feldman 1972] with others,"Recent Developments in SAIL-An Algol-Based
Language for Artificial Intelligence", (with others).
CS 308, Stanford University, August 1972.
To appear in Proc. Fall Joint Computer Conference, 1972.
[Gill] Gill, Aharon, Visual Feedback and Related Problems in Computer-
Controlled Hand Eye Coordination, AIM 178,October 1972.
[Grape 1969] "Computer Vision through Sequential Abstraction",
Artificial Intelligence Laboratory, Internal Report, 1969.
[Grape 1970] "On predicting and Verifying Missing Elements in Line-Drawings"
Artificial Intelligence Laboratory, Internal Report, March 1970.
Guzman, A. [1968] Computer recognition of three-dimensional objects
in a visual scene. MAC-TR-59 (THESIS), Project MAC, Massachusetts
Institute of Technology, Cambridge, Massachusetts, (December).
Horn, B.K.P.[1971] "The Binford-Horn Linefinder" MIT Vision Flash 16.
[Hueckel] M.H. Hueckel, "An Operator Which Locates Edges in Digitized
Pictures", Stanford Artificial Intelligence Laboratory AIM-105,
December 1969, JACM, Vol. 18, No. 1, January 1971.
Huffman, D.A. "Impossible objects as nonsense sentences" Machine
Intelligence 6.
[Minsky 1972] "Artificial Intelligence Progress Report", AI Memo 252,
MIT AI Lab, (1972);
[Nevatia 1973] R.K.Nevatia and T.O.Binford, "Structured Descriptions of
Complex Objects", Submitted to Third IJCAI, February 1973.
[Paul] R. Paul, "Trajectory Control of a Computer Arm", 2nd
International Joint Conference on Artificial Intelligence, 1971.
[Paul] R. Paul, "Modelling, Trajectory Calculation and Servoing of a
Computer Controlled Arm", Ph.D. Thesis, Computer Science Dept.,
Stanford University, Sept. 1972.
[Pingle 1972a] Karl K. Pingle, "Hand/Eye Library", Stanford
Artificial Intelligence Laboratory Operating Note 35.1, January,
1972.
[Pingle 1972b] K.K. Pingle and J.M. Tenenbaum, "An Accomodating Edge
Follower", IJCAI-2. Proceedings of the 2nd. International Symposium
on Industrial Robots, May 1972, Chicago, Illinois.
[Quam 1972] L. H. Quam, S. Liebes, Jr., R. B. Tucker, M. J. Hannah,
B. G. Eross, "Computer Interactive Picture Processing", Stanford
Artificial Intelligence Laboratory AIM-166, April 1972.
Roberts, L.G. [1963] Machine perception of three-dimensional solids.
Technical Report No. 315, Lincoln Laboratory, M.I.T. (May)
Also in Optical and Electro-Optical Information Proecesing,
Tippett, J.T. et. al.(Eds.), MIT Press, Cambridge, Mass., 1965,
[Scheinman] V. D. Scheinman, Design of a Computer Manipulator,
Stanford Artificial Intelligence Project, Memo AIM-92, June 1969.
[Sobel] Irwin Sobel, "Camera Models and Machine Perception", Stanford
Artificial Intelligence Project Memo AIM-121, May, 1970.
[Shirai 1971a] "Recognition of Polyhedra with a Range Finder"
Y. Shirai and M. Suwa, Internation Joint Conference on AI, London,
Sept 1971.
[Shirai 1972] "A heterarchical program for Recognition of Polyhedra",
Y. Shirai, Artificial Intelligence Laboratory, MIT, Memo 263.
[Swinehart] D. Swinehart, R. Sproull, "SAIL", Stanford Artificial
Intelligence Laboratory Operating Note 57, November 1969.
[Tenenbaum]
J.M.Tenenbaum,"Accommodation in Computer Vision",
Artificial Intelligence Lab, Stanford University, AIM-134 September 1970.
[Waltz] "Generating Semantic Descriptions from Drawings of Scenes
with Shadows", D.L.Waltz, Artificial Intelligence Laboratory, MIT
AI TR-271.
[Yakimovsky 1972] Y.Yakimovsky and J.A.Feldman,
"A Semantics-Based Decision Theoretic Region Analyzer"
Submitted to Third IJCAI, February,1973
VIII. RELEVANT LABORATORY PUBLICATIONS
The following articles published by members of the Stanford
Artificial Intelligence Laboratory are relevant to this proposal.
J. McCarthy, "Computer Control of a Hand and Eye," in Proc. Third
All-Union Conference on Automatic Control (Technical Cybernetics),
Nauka, Moscow, 1967 (Russian).
J. Feldman (with D. Gries), "Translator Writing Systems", Comm. ACM,
February 1968.
J. Feldman (with P. Rovner), "The Leap Language Data Structure",
Proc. IFIP Congress, 1968.
J. McCarthy, L. Earnest, D. Reddy, and P. Vicens, "A Computer with
Hands, Eyes, and Ears", Proc. AFIPS Conf. (FJCC), 1968.
K. Pingle, J. Singer, and W. Wichman, "Computer Control of a
Mechanical Arm through Visual Input", Proc. IFIP Congress 1968.
J. Feldman, G. Feldman, G. Falk, G. Grape, J. Pearlman, I. Sobel, and
J. Tenenbaum, "The Stanford Hand-Eye Project", Proc. International
Conf. on Artificial Intelligence, Washington, D.C., 1969.
J. Feldman (with P. Rovner), "An Algol-based Associative
Language", Comm. ACM, August 1969.
U. Montanari, "Continuous Skeletons from Digitized Images", JACM,
October 1969.
R. Paul, G. Falk, J. Feldman, "The Computer Representation of Simply
Described Scenes", Proc. 2ND Illinois Graphics Conference, Univ.
Illinois, April 1969.
K. Pingle, "Visual Perception by a Computer", in Automatic
Interpretation and Classification of Images, Academic Press, New
York, 1970.
U. Montanari, "A Note on Minimal Length Polygonal Approximation to a
Digitized Contour", Comm. ACM, January 1970.
U. Montanari, "On Limit Properties in Digitization Schemes", JACM,
April 1970.
U. Montanari, "Separable Graphs, Planar Graphs and Web Grammars",
Information and Control, May 1970.
U. Montenari, "Heuristically Guided Search and Chromosome Matching",
J. Artificial Intelligence, Vol. 1, No. 4, December 1970.
G. Falk, "Scene Analysis Based on Imperfect Edge Data", Proc. 2IJCAI,
Brit. Comp. Soc., Sept. 1971.
J. Feldman and R. Sproull, "System Support for the Stanford
Hand-eye System", Proc. 2IJCAI, Brit. Comp. Soc., Sept. 1971.
J. Feldman, et al, "The Use of Vision and Manipulation to Solve the
`Instant Insanity' Puzzle", Proc. 2IJCAI, Brit. Comp. Soc., Sept.
1971.
M. Hueckel, "An Operator which Locates Edges in Digitized Pictures",
JACM, January 1971.
M. Kahn and B. Roth, "The Near-minimum-time Control of Open-loop
Articulated Kinematic Chains", Trans. ASME, Sept. 1971.
U. Montanari, "On the Optimal Detection of Curves in Noisy Pictures",
Comm. ACM, May 1971.
N. Nilsson, "Problem-solving Methods in Artificial Intelligence",
McGraw-Hill, New York, 1971.
R. Paul, "Trajectory Control of a Computer Arm", Proc. 2IJCAI, Brit.
Comp. Soc., Sept. 1971.
K. Pingle and J. Tenenbaum, "An Accomodating Edge Follower", Proc.
2IJCAI, Brit. Comp. Soc., Sept. 1971.
B. Roth, "Design, Kinematics, and Control of Computer-controlled
Manipulators", Proc. 6th All Union Conference on New Problems in
Theory of Machines & Mechanics, Leningrad, Jan. 1971 (in press).
J. Tenenbaum, et, al, "A Laboratory for Hand-eye Research", Proc.
IFIP Congress 1971.
G. Falk, "Interpretation of Imperfect Line Data as a
Three-Dimensional Scene", J. Artificial Intelligence, Vol. 3, No. 2,
1972.
J. Gips, "A New Reversible Figure", Perceptual & Motor Skills, 34,
306, 1972.
IX. FILMS
Prints of the following films are available for short-term loan.
1. Art Eisenson and Gary Feldman, "Ellis D. Kroptechev and Zeus, his
Marvelous Time-Sharing System", 16mm black and white with
sound, 15 minutes, March 1967.
The advantages of time-sharing over standard batch processing are
revealed through the good offices of the Zeus time-sharing system on
a PDP-1 computer. Our hero, Ellis, is saved from a fate worse than
death. Recommended for mature audiences only.
2. Gary Feldman, "Butterfinger", 16mm color with sound, 8 minutes,
March 1968.
Describes the state of the hand-eye system at the Artificial
Intelligence Project in the fall of 1967. The PDP-6 computer getting
visual information from a television camera and controlling an
electrical-mechanical arm solves simple tasks involving stacking
blocks. The techniques of recognizing the blocks and their positions
as well as controlling the arm are briefly presented. Rated "G".
3. Raj Reddy, Dave Espar and Art Eisenson, "Hear Here", 16mm color
with sound, 15 minutes, March 1969.
Describes the state of the speech recognition project as of Spring,
1969. A discussion of the problems of speech recognition is followed
by two real time demonstrations of the current system. The first
shows the computer learning to recognize phrases and second shows how
the hand-eye system may be controlled by voice commands. Commands as
complicated as "Pick up the small block in the lower lefthand
corner", are recognized and the tasks are carried out by the computer
controlled arm.
4. Gary Feldman and Donald Peiper, "Avoid", 16mm silent, color, 5
minutes, March 1969.
Reports on a computer program written by D. Peiper for his Ph.D.
Thesis. The problem is to move the computer controlled
electrical-mechanical arm through a space filled with one or more
known obstacles. The program uses heuristics for finding a safe
path; the film demonstrates the arm as it moves through various
cluttered environments with fairly good success.
5. Richard Paul and Karl Pingle, "Instant Insanity", 16 mm color,
silent, 6 minutes, August, 1971.
Shows the hand/eye system solving the puzzle "Instant Insanity".
Sequences include finding and recognizing cubes, color recognition
and object manipulation. This film was made to accompany a paper
presented at the 1971 International Joint Conference on Artificial
Intelligence in London. It may be hard to understand without a
narrator.
6. Suzanne Kandra, "Motion and Vision", 16 mm color, sound, 22
minutes, November 1972.
A technical presentation of three research projects completed in
1972: advanced arm control by R. P. Paul [AIM-177], visual feedback
control by A. Gill [AIM-178], and representation and description of
curved objects by G. Agin [AIM-173].
X. RECENT REPORTS
The following reports have been published by the Stanford Artificial
Intelligence Laboratory since 1971.
AIM-140, Roger C. Schank, INTENTION, MEMORY, AND COMPUTER
UNDERSTANDING, January 1971, 59 pages.
Procedures are described for discovering the intention of a speaker
by relating the Conceptual Dependence representation of the speaker's
utterance to the computer's world model such that simple implications
can be made. These procedures function at levels higher than that of
structure of the memory. Computer understanding of natural language
is shown to consist of the following parts: assigning a conceptual
representation to an input; relating that representation to the
memory such as to extract the intention of the speaker; and selecting
the correct response type triggered by such an utterance according to
the situation.
AIM-141, Bruce G. Buchanan, Edward A. Feigenbaum, and Joshua
Lederberg, THE HEURISTIC DENDRAL PROGRAM FOR EXPLAINING
EMPIRICAL DATA, February 1971, 20 pages.
The Heuristic DENDRAL program uses an information processing model of
scientific reasoning to explain experimental data in organic
chemistry. This report summarizes the organization and results of the
program for computer scientists. The program is divided into three
main parts: planning, structure generation, and evaluation.
The planning phase infers constraints on the search space from the
empirical data input to the system. The structure generation phase
searches a tree whose termini are models of chemical models using
pruning heuristics of various kinds. The evaluation phase tests the
candidate structures against the original data. Results of the
program's analyses of some tests are discussed.
AIM-142, Robin Milner, AN ALGEBRAIC DEFINITION OF SIMULATION BETWEEN
PROGRAMS, February 1971, 21 pages.
A simulation relation between programs is defined which is
quasi-ordering. Mutual simulation is then an equivalence relation,
and by dividing out by it we abstract from a program such details as
how the sequencing is controlled and how data is represented. The
equivalence classes are approximations to the algorithms which are
realized, or expressed, by their member programs.
A technique is given and illustrated for proving simulation and
equivalence of programs; there is an analogy with Floyd's technique
for proving correctness of programs. Finally, necessary and
sufficient conditions for simulation are given.
AIM-143. John McCarthy, Arthur Samuel and Artificial Intelligence
Project staff, Edward Feigenbaum and Heuristic Dendral
Project staff, Project Technical Report, MARCH 1971, 80 pages.
(out of print).
An overview is presented of current research at Stanford in
artificial intelligence and heuristic programming. This report is
largely the text of a proposal to the Advanced Research Projects
Agency for fiscal years 1972-3.
AIM-144. Lynn H. Quam, COMPUTER COMPARISON OF PICTURES, May 1971,
120 pages.
This dissertation reports the development of digital computer
techniques for detecting changes in scenes by normalizing and
comparing pictures which were taken from different camera positions
and under different conditions of illumination. The pictures are
first geometrically normalized to a common point of view. Then they
are photometrically normalized to eliminate the differences due to
different illumination, camera characteristics, and reflectance
properties of the scene due to different sun and view angles. These
pictures are then geometrically registered by maximizing the cross
correlation between areas in them. The final normalized and
registered pictures are then differenced point by point.
The geometric normalization techniques require relatively accurate
geometric models for the camera and the scene, and static spatial
features must be present in the pictures to allow precise geometric
alignment using the technique of cross correlation maximization.
Photometric normalization also requires a relatively accurate model
for the photometric response of the camera, a reflectance model for
the scene (reflectance as a function of the illumination view, and
phase angles) and some assumptions about the kinds of reflectance
changes which are to be detected.
These techniques have been incorporated in a system for comparing
Mariner 1971 pictures of Mars to detect variable surface phenomena as
well as color and polarization differences. The system has been
tested using Mariner 6 and 7 pictures of Mars.
Although the techniques described in this dissertation were developed
for Mars pictures, their use is not limited to this application.
Various parts of this software package, which was developed for
interactive use on the time-sharing system of the Stanford Artificial
Intelligence Project, are currently being applied to other scenery.
AIM-145, Bruce G. Buchanan, Edward A. Feigenbaum, and Joshua
Lederberg, A HEURISTIC PROGRAMMING STUDY OF THEORY FORMATION
IN SCIENCE, June 1971, 41 pages.
The Meta-DENDRAL program is a a vehicle for studying problems of
theory formation in science. The general strategy of Meta-DENDRAL is
to reason from data to plausible generalizations and then to organize
the generalizations into a unified theory. Three main subproblems
are discussed: (1) explain the experimental data for each individual
chemical structure, (2) generalize the results from each structure to
all structures, and (3) organize the generalizations into a unified
theory. The program is built upon the concepts and programmed
routines already available in the Heuristic DENDRAL performance
program, but goes beyond the performance program in attempting to
formulate the theory which the performance program will use.
AIM-146, Andrei P. Ershov, PARALLEL PROGRAMMING, July 1971, 14 pages.
This report is based on lectures given at Stanford University by Dr.
Ershov in November, 1970.
AIM-147, Robert E. Kling, REASONING BY ANALOGY WITH APPLICATIONS TO
HEURISTIC PROBLEM SOLVING: A CASE STUDY, August 1971,
191 pages.
An information-processing approach to reasoning by analogy is
developed that promises to increase the efficiency of heuristic
deductive problem-solving systems. When a deductive problem-solving
system accesses a large set of axioms more than sufficient particular
problem, it will often create many irrelevant deductions than
saturate the memory of the problem solver.
Here, an analogy with some previously solved problem and a new
unsolved problem is used to restrict the data base to a small set of
appropriate axioms. This procedure (ZORBA) is studied in detail for
a resolution theorem proving system. A set of algorithms (ZORBA-I)
which automatically generates an analogy between a new unproved
theorem, T↓A, and a previously proved theorem, T, is described in
detail. ZORBA-I is implemented in LISP on a PDP-10.
ZORBA-I is examined in terms of its empirical performance on parts of
analogous theorems drawn from abstract algebra. Analytical studies
are included which show that ZORBA-I can be useful to aid automatic
theorem proving in many pragmatic cases while it may be a detriment
in certain specially contrived cases.
AIM-148, Edward Ashcroft, Zohar Manna, and Amir Pneuli, DECIDABLE
PROPERTIES OF MONADIC FUNCTIONAL SCHEMAS, July 1971,
10 pages.
We define a class of (monadic) functional schemas which properly
include `Ianov' flowchart schemas. We show that the termination,
divergence and freedom problems for functional schemas are decidable.
Although it is possible to translate a large class of non-free
functional schemas into equivalent free functional schemas, we show
that this cannot be done in general. We show also that the
equivalence problem for free functional schemas is decidable. Most
of the results are obtained from well-known results in Formal
Languages and Automata Theory.
AIM-149, Rodney Albert Schmidt, Jr., A STUDY OF THE REAL-TIME CONTROL
OF A COMPUTER-DRIVEN VEHICLE, August 1971, 180 pages.
Vehicle control by the computer analysis of visual images is
investigated. The areas of guidance, navigation, and incident
avoidance are considered. A television camera is used as the prime
source of visual image data.
In the guidance system developed for an experimental vehicle, visual
data is used to gain information about the vehicle system dynamics,
as well as to guide the vehicle. This information is used in real
time to improve performance of the non-linear, time-varying vehicle
system.
A scheme for navigation by pilotage through the recognition of two
dimensional scenes is developed. A method is proposed to link this
to a computer-modelled map in order to make journeys.
Various difficulties in avoiding anomolous incidents in the automatic
control of automobiles are discussed, together with suggestions for
the application of this study to remote exploration vehicles or
industrial automation.
AIM-150, Robert W. Floyd, TOWARD INTERACTIVE DESIGN OF CORRECT
PROGRAMS, September 1971, 12 pages.
We propose an interactive system proving the correctness of a
program, or locating errors, as the program is designed.
AIM-151, Ralph L. London, CORRECTNESS OF TWO COMPILERS FOR A LISP
SUBSET, October 1971, 41 pages.
Using mainly structural induction, proofs of correctness of each of
two running Lisp compilers for the PDP-10 computer are given.
Included are the rationale for presenting these proofs, a discussion
of the proofs, and the changes needed to the second compiler to
complete its proof.
AIM-152, A.W. Biermann, ON THE INFERENCE OF TURING MACHINES FROM
SAMPLE COMPUTATIONS, October 1971, 31 pages.
An algorithm is presented which when given a complete description of
a set of Turing machine computations finds a Turing machine which is
capable of doing those computations. This algorithm can serve as the
basis for designing a trainable device which can be trained to
simulate any Turing machine by being led through a series of sample
computations done by that machine. A number of examples illustrate
the use of the technique and the possibility of the application to
other types of problems.
AIM-153, Patrick J. Hayes, THE FRAME PROBLEM AND RELATED PROBLEMS IN
ARTIFICIAL INTELLIGENCE, November 1971, 18 pages.
The frame problem arises in considering the logical structure of a
robot's beliefs. It has been known for some years, but only recently
has much progress been made. The problem is described and discussed.
Various suggested methods for its solution are outlines, and
described in a uniform notation. Finally, brief consideration is
given to the problem of adjusting a belief system in the face of
evidence which contradicts beliefs. It is shown that a variation on
the situation notation of (McCarthy and Hayes, 1969) permits an
elegant approach, and relates this problem to the frame problem.
AIM-154, Zohar Manna, Stephen Ness and Jean Vuillemin, INDUCTIVE
METHODS FOR PROVING PROPERTIES OF PROGRAMS, November 1971,
24 pages.
We have two main purposes in this paper. First, we clarify and
extend known results about computation of recursive programs,
emphasizing the difference between the theoretical and practical
approaches. Secondly, we present and examine various known methods
for proving properties of recursive programs. We discuss in detail
two powerful inductive methods, computational induction and
structural induction, illustrating their applications by various
examples. We also briefly discuss some other related methods.
Our aim in this work is to introduce inductive methods to as wide a
class of readers as possible and to demonstrate their power as
practical techniques. We ask the forgiveness of our more
theoretical-minded colleagues for our occasional choice of clarity
over precision.
AIM-155, Jonathan Leonard Ryder, HEURISTIC ANALYSIS OF LARGE TREES AS
GENERATED IN THE GAME OF GO, December 1971, 300 pages.
The Japanese game of Go is of interest both as a problem in
mathematical repesentation and as a game which generates a move tree
with an extraordinarily high branching factor (100 to 300 branches
per ply). The complexity of Go (and the difficulty of Go for human
players) is thought to be considerably greater than that of chess.
The constraints of being able to play a complete game and of being
able to produce a move with a moderate amount of processing time were
placed on the solution.
The basic approach used was to find methods for isolating and
exploring several sorts of relevant subsections of the global game
tree. This process depended heavily on the ability to define and
manipulate the entities of Go as recursive functions rather than as
patterns of stones. A general machine-accessible theory of Go was
developed to provide context for program evaluations.
A program for playing Go is now available on the Stanford PDP-10
computer. It will play a complete game, taking about 10 to 30
seconds for an average move. The quality of play is better than that
of a beginner in many respects, but incompletenesses in the current
machine-representable theory of Go prevent the present program from
becoming a strong player.
AIM-156, Kenneth Mark Colby, Franklin Dennis Hilf, Sylvia Weber, and
Helena C. Kraemer, A RESEMBLANCE TEST FOR THE VALIDATION
OF A COMPUTER SIMULATION OF PARANOID PROCESSES,
November 1971, 29 pages.
A computer simulation of paranoid processes in the form of a dialogue
algorithm was subjected to a validation study using an experimental
resemblance test in which judges rate degrees of paranoia present in
initial psychiatric interviews of both paranoid patients and of
versions of the paranoid model. The statistical results indicate a
satisfactory degree of resemblance between the two groups of
interviews. It is concluded that the model provides a successful
simulation of naturally occuring paranoid processes.
AIM-157, Yorick Wilks, ONE SMALL HEAD----SOME REMARKS ON THE USE OF
`MODEL' IN LINGUISTICS, December 1971, 17 pages.
I argue that the present situation in formal linguistics, where much
new work is presented as being a "model of the brain", or of "human
language behavior", is an undesirable one. My reason for this
judgement is not the conservative (Braithwaitian) one that the
entities in question are not really models but theories. It is
rather that they are called models because they cannot be theories of
the brain at the present stage of brain research, and hence that the
use of "model" in this context is not so much aspirational as
resigned about our total ignorance of how the brain stores and
processes linguistic information. The reason such explanatory
entities cannot be theories is that this ignorance precludes any
"semantic ascent" up the theory; i.e., interpreting the items of the
theory in terms of observables. And the brain items, whatever they
may be, are not, as Chomsky has sometimes claimed, in the same
position as the "occult entities" of Physics like Gravitation; for
the brain items are not theoretically unreachable, merely unreached.
I then examine two possible alternate views of what linguistic
theories should be proffered as theories of: theories of sets of
sentences, and theories of a particular class of algorithms. I argue
for a form of the latter view, and that its acceptance would also
have the effect of making Computational Linguistics a central part of
Linguistics, rather than the poor relation it is now.
I examine a distinction among "linguistic models" proposed recently
by Mey. who was also arguing for the self-sufficiency of
Computational Linguistics, though as a "theory of performance". I
argue that his distinction is a bad one, partly for the reasons
developed above and partly because he attempts to tie it to Chomsky's
inscrutable competance-performance distinction. I conclude that the
independence and self-sufficiency of Computational Linguistics are
better supported by the arguments of this paper.
AIM-158, Zohar Manna, Ashok Chandra, PROGRAM SCHEMAS WITH EQUALITY,
December 1971, 22 pages.
We discuss the class of program schemas augmented with equality
tests, that is, tests of equality between terms. In the first part
of the paper we illustrate the "power" of equality tests. It turns
out that the class of program schemas with equality is more powerful
than the "maximal" classes of schemas suggested by other
investigators. In the second part of the paper, we discuss the
decision problems of program schemas with equality. It is shown, for
example, that while the decision problems normally considered for
schemas (such as halting, divergence, equivalence, isomorphism and
freedom) are decidable for ianov schemas. They all become
undecidable if general equality tests are added. We suggest,
however, limited equality tests which can be added to certain
subclasses of program schemas while preserving their decidability
property.
AIM-159, J.A. Feldman and Paul C. Shields, TOTAL COMPLEXITY AND
INFERENCE OF BEST PROGRAMS, April 1972.
Axioms for a total complexity measure for abstract programs are
presented. Essentially, they require that total complexity be an
unbounded increasing function of the Blum time and size measures.
Algorithms for finding the best program on a finite domain are
presented, and their limiting behavior for infinite domains
described. For total complexity, there are important senses in which
a machine can find the best program for a large class of functions.
AIM-160, J. Feldman, AUTOMATIC PROGRAMMING, February 1972, 20 pages.
The revival of interest in Automatic Programming is considered. The
research is divided into direct efforts and theoretical developments
and the successes and prospects of each are described.
AIM-161, Y. Wilks, AN ARTIFICIAL INTELLIGENCE APPROACH TO MACHINE
TRANSLATION, February 1972, 44 pages.
The paper describes a system of semantic analysis and generation,
programmed in LISP 1.5 and designed to pass from paragraph length
input in English to French via an interlingual representation. A
wide class of English input forms will be covered, but the vocabulary
will initially be restricted to one of a few hundred words. With
this subset working, and during the current year (1971-72), it is
also hoped to map the interlingual representation onto some predicate
calculus notation so as to make possible the answering of very simple
questions about the translated matter. The specification of the
translation system itself is complete, and its main points are:
i) It translates phrase by phrase--with facilities for reordering
phrases and establishing essential semantic connectivities between
them--by mapping complex semantic stuctures of "message" onto each
phrase. These constitute the interlingual representation to be
translated. This matching is done without the explicit use of a
conventional syntax analysis, by taking as the appropriate matched
structure the "most dense" of the alternative structures derived.
This method has been found highly successful in earlier versions of
this analysis system.
ii) The French output strings are generated without the explicit use
of a generative grammar. That is done by means of STEREOTYPES:
strings of French words, and functions evaluating to French words,
which are attached to English word senses in the dictionary and built
into the interlingual representation by the analysis routines. The
generation program thus receives an interlingual representation that
already contains both French output and implicit procedures for
assembling the output, since the stereotypes are in effect recursive
procedures specifying the content and production of the output word
strings. Thus the generation program at no:time consults a word
dictionary or inventory of grammar rules.
It is claimed that the system of notation and translation described
is a convenient one for expressing and handling the items of semantic
information that are ESSENTIAL to any effective MT system. I discuss
in some detail the semantic information needed to ensure the correct
choice of output prepositions in French; a vital matter inadequately
treated by virtually all previous formalisms and projects.
AIM-162, Roger Schank, Neil Goldman, Chuck Reiger, Chris Reisbeck,
PRIMITIVE CONCEPTS UNDERLYING VERBS OF THOUGHT,
April 1972, 102 pages.
In order to create conceptual structures that will uniquely and
unambiguously represent the meaning of an utterance, it is necessary
to establish `primitive' underlying actions and states into which
verbs can be mapped. This paper presents analyses of the most common
mental verbs in terms of such primitive actions and states. In order
to represent the way people speak about their mental processes, it
was necessary to add to the usual ideas of memory structure the
notion of Immediate Memory. It is then argued that there are only
three primitive mental ACTs.
AIM-163, J.M. Cadiou, RECURSIVE DEFINITIONS OF PARTIAL FUNCTIONS AND
THEIR COMPUTATIONS, April 1972, 160 pages.
A formal syntactic and semantic model is presented for `recursive
definitions' which are generalizations of those found in LISP, for
example. Such recursive definitions can have two classes of
fixpoints, the strong fixpoints and the weak fixpoints, and also
possess a class of computed partial functions.
Relations between these classes are presented: fixpoints are shown
to be extensions of computed functions. More precisely, strong
fixpoints are shown to be extensions of computed functions when the
computations may involve "call by name" substitutions; weak
fixpoints are shown to be extensions of computed functions when the
computation only involve "call by value" substitutions. The
Church-Rosser property for recursive definitions with fixpoints also
follows from these results.
Then conditions are given on the recursive definitions to ensure that
they possess least fixpoints (of both classes), and computation rules
are given for computing these two fixpoints: the "full" computation
rule, which leads to the least weak fixpoint. A general class of
computation rules, called `safe innermost', also lead to the latter
fixpoint. The "leftmost innermost" rule is a special case of those,
for the LISP recursive definitions.
AIM-164, Zohar Manna and Jean Vuillemin, FIXPOINT APPROACH TO THE
THEORY OF COMPUTATION, April 1972, 29 pages.
Substantial effort has been put into finding verification techniques
for computer programs. There are now so many verification techniques
that a choice in a practical situation may appear difficult to the
non-specialist. In particular, the most widely used methods, such as
the "inductive assertion method", can be used to prove some
input-output relation (assuming that the program terminates) while
such problems as termination or equivalence usually require a
different type of technique.
Our main purpose in this paper is to suggest that Scott's fixedpoint
approach to the semantics of programming languages frees us from that
dilemma. It allows one not only to justify all existing verification
techniques, but also to extend them to handle other properties of
computer programs, including termination and equivalence, in a
uniform manner.
AIM-165, D,A, Bochvar, TWO PAPERS ON PARTIAL PREDICATE CALCULUS,
April 1972, 50 pages.
The three-valued system to which this study is devoted is of interest
as a logical calculus for two reasons: first, it is based on
formalization of certain basic and intuitively obvious relations
satisfied by the predicates "true", "false" and "meaningless" as
applied to propositions, and as a result the system possesses a
clear-cut and intrinsically logical interpretation; second, the
system provides a solution to a specifically logical problem,
analysis of the paradoxes of classical mathematical logic, by
formally proving that certain propositions are meaningless.
The paper consists of three parts. In the first we develop the
elementary part of the system--the propositional calculus--on the
basis of intuitive considerations. In the second part we outline the
"restricted" functional calculus corresponding to the propositional
calculus. The third and last part uses a certain "extension" of the
functional calculus to analyze the paradoxes of classical
mathematical logic.
We are indebted to Professor V.I. Glivenko for much valuable advice
and criticism. In particular, he provided a more suitable definition
of the function a(see I, Section 2, subsection 1.).
AIM 166, Lynn H. Quam, Sidney Liebes, Jr., Robert B. Tucker, Marsha
Jo Hannah, Botond G. Eross, COMPUTER INTERACTIVE PICTURE
PROCESSING, April 1972, 40 pages.
This report describes work done in image processing using an
interactive computer system. Techniques for image differencing are
described and examples using images returned from Mars by the Mariner
Nine spacecraft are shown. Also described are techniques for stereo
image processing. Stereo processing for both conventional camera
systems and the Viking 1975 Lander camera system is reviewed.
AIM-167, Ashok Chandra, EFFICIENT COMPILATION OF LINEAR RECURSIVE
PROGRAMS, June 1972, 43 pages.
We consider the class of linear recursive programs. A linear
recursive program is a set of procedures where each procedure can
make at most one recursive call. The conventional stack
implementation of recursion requires time and space both proportional
to n, the depth of recursion. It is shown that in order to
implement linear recursion so as to execute in time n one doesn't
need space proportional to n: n**ε for sufficiently small ε will do.
It is also known that with constant space one can implement linear
recursion in time n**2. We show that one can do much better:
n**(1+ε) for arbitrarily small ε. We also describe an algorithm that
lies between these two: it takes time n*log n and space log n.
It is shown that several problems are closely related to the linear
recursion problem, for example, the problem of reversing an input
tape given a finite automaton with several one-way heads. By casting
all these problems into canonical form, efficient solutions are
obtained simultaneously for all.
AIM-168, Shigeru Igarashi, ADMISSIBILITY OF FIXED-POINT INDUCTION IN
FIRST-ORDER LOGIC OF TYPED THEORIES, May 1972, 40 pages.
First-order logic is extended so as to deal with typed theories,
especially that of continuous functions with fixed-point induction
formalized by D. Scott. The translation of his formal system, or the
λ calculus-oriented system derived and implemented by R. Milner, into
this logic amounts to adding predicate calculus features to them.
In such a logic the fixed-point induction axioms are no longer valid,
in general, so that we characterize formulas for which Scott-type
induction is applicable, in terms of syntax which can be checked
by machines automatically.
Diskfile: Aim168.igr[aim,doc.)
AIM-169, Robin Milner, LOGIC FOR COMPUTABLE FUNCTIONS. DESCRIPTION
OF A MACHINE IMPLEMENTATION, May 1972, 36 pages.
This paper is primarily a user's manual for LCF, a proof-checking
program for a logic of computable functions proposed by Dana Scott in
1969, but unpublished by him. We use the name LCF also for the logic
itself, which is presented at the start of the paper. The
proof-checking program is designed to allow the user interactively to
generate formal proofs about computable functions and functionals
over a variety of domains, including those of interest to the
computer scientist--for example, integers, lists and computer
programs and their semantics. The user's task is alleviated by two
features: a subgoaling facility and a powerful simplification
mechanism. Applications include proofs of program correctness and in
particular of compiler correctness; these applications are not
discussed herein, but are illustrated in the papers referenced in the
introduction.
Diskfile: Lcfman.rgm[aim,doc]
AIM-170, Yorick Wilks, LAKOFF ON LINGUISTICS AND NATURAL LOGIC,
June 1972, 19 pages.
The paper examines and criticises Lakoff's notions of a natural logic
and of a generative semantics described in terms of logic, I argue
that the relationship of these notions to logic as normally
understood is unclear, but I suggest, in the course of the paper, a
number of possible interpretations of his thesis of generative
semantics. I argue further that on these interpretations a mere
notational variant of Chomskyan theory, I argue, too, that Lakoff's
work may provide a service in that it constitutes a reductio ad
absurdum of the derivational paradigm of modern linguistics; and
shows, inadvertently, that only a system with the ability to
reconsider its own inferences can do the job that Lakoff sets up for
linguistic enquirey -- that is to say, only an "artificial
intelligence" system.
Diskfile: Lakoff.Yaw[aim,doc]
AIM-171, Roger Schank, ADVERBS AND BELIEF, June 1972, 30 pages.
The treatment of a certain class of adverbs in conceptual
representation is given. Certain adverbs are shown to be
representative of complex belief structures. These adverbs serve as
pointers that explain where the sentence that they modify belongs in
a belief structure.
AIM-172, Sylvia Weber Russell, SEMANTIC CATEGORIES OF NOMINALS FOR
CONCEPTUAL DEPENDENCY ANALYSIS OF NATURAL LANGUAGE, July 1972,
64 pages.
A system for the semantic categorization of conceptual objects
(nominals) is provided. The system is intended to aid computer
understanding of natural language. Specific implementations for
"noun-pairs" and prepositional phrases are offered.
AIM-173, Gerald Jacob Agin, REPRESENTATION AND DESCRIPTION OF CURVED
OBJECTS, October 1972,
This document describes some first efforts toward the goal of
description and recognition of the general class of curved, three
dimensional objects.
Three dimensional images, similar to depth maps, are obtained with a
triangulation system using a television camera, and a deflectable
laser beam diverged into a plane by a cylindrical lens.
Complex objects are represented as structures joining parts called
generalized cylinders. These primitives are formalized in a volume
representation by an arbitrary cross section varying along a space
curve axis. Several types of joint structures are discussed.
Experimental results are shown for the description (building of
internal computer models) of a handful of complex objects, beginning
with laser range data from actual objects. our programs have
generated complete descriptions of rings, cones, and snake-like
objects, all of which may be described by a single primitive. Complex
objects, such as dolls, have been segmented into parts, most of which
are well described by programs which implement generalized cylinder
descriptions.
AIM-174, Morris, Francis Lockwood, CORRECTNESS OF TRANSLATIONS OF
PROGRAMMING LANGUAGES -- AN ALGEBRAIC APPROACH, August 1972,
124 p.
Programming languages and their sets of meanings can be modelled by
general operator algebras; semantic functions and compiling functions
by homomorphisms of operator algebras. A restricted class of
individual programs, machines, and computations can be modelled in a
uniform manner by binary relational algebras. A restricted class of
individual manner by binary relational algebras. These two
applications of algebra to computing are compatible: the semantic
function provided by interpreting ("running") one binary relational
algebra on another is a homomorphism on an operator algebra whose
elements are binary relational algebras.
Using these mathematical tools, proofs can be provided systematically
of the correctness of compilers for fragmentary programming languages
each embodying a single language "feature". Exemplary proofs are
given for statement sequences, arithmetic expressions, Boolean
expressions, assignment statements, and while statement. Moreover,
proofs of this sort can be combined to provide (synthetic) proofs for
in principle, many different complete programming languages. One
example of such a synthesis is given.
AIM-175, Tanaka, Hozumi, HADAMARD TRANSFORM FOR SPEECH WAVE ANALYSIS,
August 1972, 34 pages.
Two methods of speech wave analysis using the Hadamard transform are
discussed. The first method is a direct application of the Hadamard
transform for speech waves. The reason this method yields poor
results is discussed. The second method is the application of the
Hadamard transform to a log-magnitude frequency spectrum. After the
application of the Fourier transform the Hadamard transform is
applied to detect a pitch period or to get a smoothed spectrum. This
method shows some positive aspects of the Hadamard transform for the
analysis of a speech wave with regard to the reduction of processing
time required for smoothing, but at the cost of precision. A formant
tracking program for voiced speech is implemented by using this
method and an edge following technique used in scene analysis.
AIM-176, Feldman, J.A., Low, J.R., Swinehart, D.C., Taylor, R.H.,
RECENT DEVELOPMENTS IN SAIL. AN ALGOL-BASED LANGUAGE FOR
ARTIFICIAL INTELLIGENCE, (forthcoming).
AIM-177, Paul, Richard, MODELLING, TRAJECTORY CALCULATION AND SERVOING
OF A COMPUTER CONTROLLED ARM, (forthcoming)
AIM-178, Gill, Aharon, VISUAL FEEDBACK AND RELATED PROBLEMS IN COMPUTER
CONTROLLED HAND EYE COORDINATION, October 1972, 134 pages.
A set of programs for precise manipulation of simple planar bounded
objects, by means of visual feedback, was developed for use in the
Stanford hand-eye system. The system includes a six degrees of
freedom computer controlled manipulator (arm and hand) and a fully
instrumented computer television camera.
The image of the hand and manipulated objects is acquired by the
computer through the camera. The stored image is analyzed using a
corner and line finding program developed for this purpose. The
analysis is simplified by using all the information available about
the objects and the hand, and previously measured coordination
errors. Simple touch and force sensing by the arm help the
determination of three dimensional positions from one view.
The utility of the information used to simplify the scene analysis
depends on the accuracy of the geometrical models of the camera and
arm. A set of calibration updating techniques and programs was
developed to maintain the accuracy of the camera model relative to
the arm model.
The precision obtained is better than .1 inch. It is limited by the
resolution of the imaging system and of the arm position measuring
system.
AIM-179, Baumgart, Bruce G., WINGED EDGE POLYHEDRON REPRESENTATION,
October 1972, 46 pages.
(forthcoming)
AIM-180, Bajcsy, Ruzena, COMPUTER IDENTIFICATION OF TEXTURED VISUAL
SCENES, October 1972, 156 pages.
This work deals with computer analysis of textured outdoor scenes
involving grass, trees, water and clouds. Descriptions of texture are
formalized from natural language descriptions; local descriptors are
obtained from the directional and non-directional components of the
Fourier transform power spectrum. Analytic expressions are obtained
for orientation, contrast, size, spacing, and in periodic cases, the
locations of texture elements. These local descriptors are defined
over windows of various sizes; the choice of sizes is made by a
simple higher- level program.
The process of region growing is represented by a sheaf-theoretical
model which formalizes the operation of pasting local structure (over
a window) into global structure (over a region). Programs were
implemented which form regions of similar color and similar texture
with respect to the local descriptors.
An interpretation is made of texture gradient as distance gradient
in space. A simple world model is described. An interpretation of
texture regions and texture gradient is made with a simulated
correspondence with the world model. We find that a problem-solving
approach, involving hypothesis-verification, more satisfactory than
an earlier pattern recognition effort (Bajcsy 1970) and more crucial
to work with complex scenes than in scenes of polyhedra. Geometric
clues from relative sizes, texture gradients, and interposition are
important in interpretation.
XI. COGNIZANT PERSONNEL
For contractual matters:
Office of the Research Administrator
Stanford University
Stanford, California 94305
Telephone: (415) 321-2300, ext. 2883
For technical and scientific matters:
Prof. Jerome Feldman
Computer Science Department
Stanford University
Stanford, California 94305
Telephone: (415) 321-2300, ext. 4971
For administrative matters, including questions
relating to the budget or property acquisition:
Mr. Lester D. Earnest, Executive Officer
Mr. Norman R. Briggs, Business Manager
Artificial Intelligence Laboratory
Stanford University
Stanford, California 94305
Telephone: (415) 321-2300, ext. 4971